#include<stdio.h>
#include<stdlib.h> 
#include<math.h>
#include<vector>
#include<map>
#include<set>
#define LEN     60
#define EDGE_NUM (rst->gx)*(rst->gy - 1) + (rst->gy)*(rst->gx - 1)
#define INFTY   2147483647

using   namespace       std;
void    update_hist ( routingInst *rst )
{
        for ( int i = 0; i<rst->numEdges; i++ )
        {
                if ( rst->edgeUtils[i] > rst->edgeCaps[i] )
                        rst->hist[i]  = rst->hist[i]+1.5;
        }
}
float   dfn_weight ( int util, int cap, float hist )
{ 
        if ( cap )
                return  1+hist*(util+1)/cap;
        else
                return  100000;
}

//      
//      some basic functions in graph
//
point   id_to_pt ( int id, routingInst *rst )
{
        point   p;
        p.x = id % (rst->gx);
        p.y = id / (rst->gx);
        return  p;
}
int     pos_to_id ( int x, int y, routingInst *rst )
{
        return y*(rst->gx)+x;
}
int     pt_to_id ( point pt, routingInst *rst )
{
        return  pt.y*(rst->gx)+pt.x;
}
int     find_edge_id (int x1, int y1, int x2, int y2, routingInst *rst )
{
        int     x,y;
        if ( y1 == y2 )
        {
                y = y1;
                x = min (x1, x2);
                return  ((rst->gx)-1)*y + x;
        }
        if ( x1 == x2 ) 
        {
                x = x1;
                y = min ( y1, y2 );
                return  ((rst->gx)-1)*(rst->gy)+(rst->gx)*y + x;
        }
        return -1;
}
int     pt_dist ( int id1, int id2, routingInst *rst )
{
        point   p1 = id_to_pt ( id1, rst );
        point   p2 = id_to_pt ( id2, rst );
        return  abs(p1.x - p2.x)+abs(p1.y - p2.y);
}
int     is_in_line ( int id1, int id2, int id3, routingInst *rst )
{
        int     gx = rst->gx;
        if ( (id1/gx==id2/gx) && (id2/gx==id3/gx ) )
                return  1;
        if ( (id1%gx==id2%gx) && (id2%gx==id3%gx ) )
                return  1;
        return  0; 
}
int     pins_within_bb ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        int     xmax = 0, xmin = rst->gx;
        int     ymax = 0, ymin = rst->gy;
        for ( int i = 0; i < n->numPins; i++ )
        {
                int     x = n->pins[i] % rst->gx;
                int     y = n->pins[i] / rst->gx;
                xmin = min ( xmin, x );
                xmax = max ( xmax, x );
                ymin = min ( ymin, y );
                ymax = max ( ymax, y );
        }
        int     c = 0;
        for ( int i = xmin; i<=xmax; i++ )
                for ( int j = ymin; j <= ymax; j++ )
                        if ( rst->nodeUtils[j*rst->gx+i])
                                ++ c;
        return  c;
}
void    pin_ordering ( int net_id, routingInst *rst )
{
        /* to find shortest path passing all nodes in net */
        net             *n = rst->nets + net_id;
        int             NUM = rst->nets[net_id].numPins;
        vector<int>     pins = rst->nets[net_id].pins;
        vector<int>     state;
        for ( int i = 0; i<NUM; i++ )
                state.push_back(0);
        int     dist = INFTY;

        int     pt1 = 0;
        int     pt2 = 0;
        for ( int i = 0; i<NUM; i++ )
                for ( int j =0; j<NUM; j++ )
                        if ( (i!=j) && pt_dist ( pins[i], pins[j], rst ) < dist )
                        {
                                dist = pt_dist(pins[i],pins[j], rst);
                                pt1 = i;        pt2 = j;
                        }
        state[pt1] = 1; 
        state[pt2] = 1;
        n->r[0].s = pins[pt1];
        n->r[0].t = pins[pt2];
        n->r[0].state = 0;
        int     k = 1;
        while ( k < NUM-1 )
        {
                int     dist = INFTY;
                for ( int i = 0; i<NUM; i++ )
                        for ( int j = 0; j<NUM; j++ )
                                if ( state[i] && !state[j] && pt_dist(pins[i],pins[j],rst)<dist )
                                {
                                        dist = pt_dist ( pins[i], pins[j], rst );
                                        pt1 = i;        pt2 = j;
                                }
                state[pt2] = 1;
                n->r[k].s = pins[pt1];
                n->r[k].t = pins[pt2];
                n->r[k].state = 0;
                k ++;
        }

}
int     is_flat ( int id1, int id2, routingInst *rst )
{
        return  (id1/rst->gx == id2/rst->gx)||(id1%rst->gx == id2%rst->gx);
}

bool    comparator_0 ( const pair<int,int> &left, const pair<int,int> &right )
{
        return  left.second < right.second;
}
bool    comparator_1 ( const score& left, const score& right )
{
        return  left.first < right.first;
}
bool    comparator_2 ( const score& left, const score& right )
{
        return  left.second > right.second;
}

void    ld_edgeWeights ( routingInst *rst )
{
        for ( int i = 0; i<rst->numEdges; i++ )
                rst->edgeWeights[i] = dfn_weight ( rst->edgeUtils[i], rst->edgeCaps[i], rst->hist[i] );
}
void    ld_netWeights ( int net_id, routingInst *rst )
{ 
        float   tot = 0;
        net     *n = rst->nets + net_id;
        for ( set<int>::iterator it = n->edges.begin(); it != n->edges.end(); ++it )
                tot += rst->edgeWeights[*it];
        rst->netWeights[net_id].second = tot;
}
void    refresh ( routingInst *rst )
{
        int     numNets = rst->numNets;
        ld_edgeWeights (rst);
        for ( int i = 0; i<numNets; i++ )
                ld_netWeights ( i, rst );
        update_hist ( rst );
}
int     ofl     ( routingInst *rst )
{
        int     ofl=0;
        for (int i=0; i<rst->numEdges; i++)
                if ( rst->edgeUtils[i] > rst->edgeCaps[i] )
                {
                        ofl += (rst->edgeUtils[i] - rst->edgeCaps[i]);
                }
        return  ofl;
}

/* Print Results */

void    ptr_edge ( FILE *fp, int id, routingInst *rst )
{
        point   p1, p2;
        if ( id <= (rst->gx-1) * rst->gy -1 )
        {
                int     y = id / ( rst->gx - 1 );
                p1.y = y;       p2.y = y;
                int     x = id % ( rst->gx - 1 );
                p1. x = x;      p2.x = x+1;
        }
        else
        {
                id = id - (rst->gx - 1 )*rst->gy;
                int     y = id / rst->gx;
                p1.y = y;       p2.y = y+1;
                int     x = id % rst->gx;
                p1. x = x;      p2.x = x;
        }
        fprintf ( fp, "(%d,%d)-(%d,%d)\n", p1.x, p1.y, p2.x, p2.y );
}       
void    print_single_net ( FILE *fp, int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        fprintf ( fp, "n%d\n", net_id );
        for ( set<int>::iterator it = n->edges.begin(); it!=n->edges.end(); ++it )
                ptr_edge ( fp, *it, rst );
        fprintf ( fp, "!\n" );
}
void    ptr_rst ( FILE *fp, routingInst *rst )
{
        for ( int i = 0; i<rst->numNets; i++ )
                print_single_net ( fp, i, rst );
}

void    ld_seg_net ( vector<int>::const_iterator beg, vector<int>::const_iterator end , int net_id, routingInst* rst )
{
        while ( beg != end )
        {
                rst->nets[net_id].edges.insert ( *beg++ );
        }
}
segment simple_segment ( int s, int t, routingInst *rst )
{
        segment         seg;
        seg.s = s;
        seg.t = t;
        point   p1 = id_to_pt ( s, rst );
        point   p2 = id_to_pt ( t, rst );

        if ( p1.y == p2.y )
        {
                for ( int x = min(p1.x, p2.x); x < max(p1.x, p2.x); x++)
                {
                        int     edge_id = find_edge_id (x,p1.y,x+1,p2.y,rst);
                        seg.edges.push_back(edge_id);
                }
                return seg;
        }
        if ( p1.x == p2.x )
        {
                for ( int y = min(p1.y, p2.y); y < max(p1.y, p2.y); y++)
                {
                        int     edge_id = find_edge_id (p1.x,y,p2.x,y+1,rst);
                        seg.edges.push_back(edge_id);
                }
                return seg;
        }
        return  seg;
}
void    simple_connect ( int s, int t, int net_id, routingInst *rst )
{
        net     *n = rst->nets+net_id;
        point   p1 = id_to_pt ( s, rst );
        point   p2 = id_to_pt ( t, rst );

        if ( p1.y == p2.y )
                for ( int x = min(p1.x, p2.x); x < max(p1.x, p2.x); x++)
                {
                        int     edge_id = find_edge_id (x,p1.y,x+1,p2.y,rst);
                        n->edges.insert ( edge_id );
                }
        if ( p1.x == p2.x )
                for ( int y = min(p1.y, p2.y); y < max(p1.y, p2.y); y++)
                {
                        int     edge_id = find_edge_id (p1.x,y,p2.x,y+1,rst);
                        n->edges.insert ( edge_id );
                }
}
int     est_segment ( segment *seg, int net_id, routingInst *rst )
{
        int     est_ofl = 0;
        net     *n = rst->nets + net_id;
        for ( vector<int>::iterator it = seg->edges.begin(); it != seg->edges.end(); ++it )
        {
                int     edge_id = *it;
                if ( ( n->edges.find(edge_id) == n->edges.end() ) &&  (rst->edgeUtils[edge_id]>=rst->edgeCaps[edge_id]) )
                        ++ est_ofl;
        }
        return  est_ofl;
}
void    Z_route ( route *r, int net_id, routingInst *rst )
{
        // only consider Z-shape
        int     s = r->s;
        int     t = r->t;
        r->state = 1;
        if ( is_flat ( s, t, rst ) )
                simple_connect(s,t,net_id,rst);
        else
        {
                int     gx = rst->gx;
                int     dist = INFTY;
                int     c1 = -1;
                int     c2 = -1;
                segment sz1, sz2, sz3;
                if ( s%gx != t%gx ) 
                        for ( int k = min(s%gx,t%gx); k<=max(s%gx,t%gx); k++ )
                        {
                                int     s1 = gx*(s/gx)+k; 
                                int     t1 = gx*(t/gx)+k;
                                segment seg1 = simple_segment (s,s1,rst );
                                segment seg2 = simple_segment (s1,t1,rst );
                                segment seg3 = simple_segment (t1,t,rst );
                                if ( est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst)<dist )
                                {
                                        c1 = s1;        c2 = t1;
                                        dist = est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst);
                                        sz1 = seg1;     sz2 = seg2;     sz3 = seg3;
                                }
                        }
                if ( s/gx != t/gx )
                        for ( int k = min(s/gx,t/gx); k<=max(s/gx,t/gx); k++ )
                        {
                                int     s1 = gx*k+(s%gx); 
                                int     t1 = gx*k+(t%gx);
                                segment seg1 = simple_segment (s,s1,rst );
                                segment seg2 = simple_segment (s1,t1,rst );
                                segment seg3 = simple_segment (t1,t,rst );
                                if ( est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst)<dist )
                                {
                                        c1 = s1;        c2 = t1;
                                        dist = est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst);
                                        sz1 = seg1;     sz2 = seg2;     sz3 = seg3;
                                }
                        }
                simple_connect ( s, c1, net_id, rst );
                simple_connect ( c1, c2, net_id, rst );
                simple_connect ( c2, t, net_id, rst );
        }
        for ( vector<segment>::iterator it = r->seg.begin(); it != r->seg.end(); ++ it )
                ld_seg_net ( (*it).edges.begin(), (*it).edges.end(), net_id, rst );
}
void    simple_net ( int net_id, routingInst *rst )
{
        net     *n = rst->nets+net_id;
        int     numPins = n->numPins;
        n->status = 1;
        for ( int i = 0; i < numPins-1; i++ )
                Z_route ( n->r+i, net_id, rst );
        for ( set<int>::iterator it = n->edges.begin(); it != n->edges.end(); ++ it )
        {
                int     id = *it;
                ++ rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight( rst->edgeUtils[id], rst->edgeCaps[id], rst->hist[id] );
        }
}
//      RRR
void    rip_up ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        n->status = 0;
        for ( set<int>::iterator it = n->edges.begin(); it!=n->edges.end(); ++it )
        {
                int     id = *it;
                -- rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight( rst->edgeUtils[id], rst->edgeCaps[id], rst->hist[id] );
        }
//        for ( int i = 0; i < n->numPins-1; i++ )
//                n->r[i].state = 0;
        n->edges.clear();
}
vector<int>     neighbor ( int id, int xmin, int ymin, int xmax, int ymax, routingInst *rst )
{
        vector<int>     Adj;
        Adj.clear();
        int     gx = rst->gx;
        int     x = id % gx;
        int     y = id / gx;
        if ( x > xmin )          // left neighbor
                Adj.push_back(y*gx+x-1);
        if ( x < xmax )       // right neighbor
                Adj.push_back(y*gx+x+1);
        if ( y > ymin )          // down neighbor
                Adj.push_back((y-1)*gx+x);
        if ( y < ymax )       // up neighbor
                Adj.push_back((y+1)*gx+x);
        return  Adj;
}
void    retrace ( std::map <int,int> &pi, int start, int goal, int net_id, route *r, routingInst *rst )
{
        int     cur = goal;
        net     *n = rst->nets + net_id; 
        
        while ( cur != start )
        {
                int     edge_id = find_edge_id ( cur%rst->gx, cur/rst->gx, pi[cur]%rst->gx, pi[cur]/rst->gx, rst );
                n->edges.insert ( edge_id );
                cur = pi[cur];
        }

}
void    A_star_route ( route *r, int net_id, routingInst *rst, float factor )
{
        int     start =r->s;
        int     goal = r->t;
        r->state = 1;
        point   ps = id_to_pt ( start, rst );
        point   pt = id_to_pt ( goal, rst );

        int     x_min = min ( ps.x, pt.x );
        int     x_max = max ( ps.x, pt.x );
        int     y_min = min ( ps.y, pt.y );
        int     y_max = max ( ps.y, pt.y );
        int     bandx = (int)factor * (x_max-x_min ) + 1;
        int     bandy = (int)factor * (y_max-y_min ) + 1;
        int     xmin = max (x_min-bandx, 0);
        int     ymin = max (y_min-bandy, 0);
        int     xmax = min (x_max+bandx, rst->gx-1);
        int     ymax = min (y_max+bandy, rst->gy-1);

        map < int, float > d;
        map < int, float > f;
        map < int, int > g;
        map < int, int > pi;
        d.clear();
        f.clear();
        g.clear();
        pi.clear();
        for ( int x = xmin; x <= xmax; ++x )
                for ( int y = ymin; y <= ymax; ++y )
                {
                        d.insert ( make_pair ( y*rst->gx+x, INFTY ) );
                        f.insert ( make_pair ( y*rst->gx+x, INFTY ) );
                        g.insert ( make_pair ( y*rst->gx+x, 1 ) );
                        pi.insert ( make_pair ( y*rst->gx+x, -1 ) );
                }
        d[start] = 0;
        f[start] = 0;

        vector  < pair<int, float> >    PQ;
        vector  < pair<int, float> >::iterator    it_PQ;
        PQ.clear();
        PQ.insert(PQ.begin(),make_pair(start, f[start]));

        while ( !PQ.empty() )
        {
                int     u = PQ.front().first;
                PQ.erase ( PQ.begin() );

                if ( u == goal )
                {
                        retrace ( pi, start, goal, net_id, r, rst );
                        return;
                }
                g[u] = 3;
                vector<int>     Adj = neighbor( u, xmin, ymin, xmax, ymax, rst );
                for ( vector<int>::iterator it = Adj.begin(); it != Adj.end(); ++it )
                {
                        int     v = *it;
                        int     edge_id = find_edge_id ( u%rst->gx, u/rst->gx, v%rst->gx, v/rst->gx, rst );
                        float   temp = d[u] + rst->edgeWeights[edge_id];
                        if ( g[v] == 3 && d[v]<=temp )
                                continue;
                        if ( g[v] != 2 || d[v]>temp )
                        {
                                pi[v] = u;
                                d[v] = temp;
                                f[v] = d[v] + pt_dist (v,goal,rst);
                                if ( g[v] != 2 )
                                {
                                        for ( it_PQ = PQ.begin(); it_PQ != PQ.end(); ++it_PQ )
                                                if ( f[v] <= (*it_PQ).second )
                                                {
                                                        PQ.insert ( it_PQ, make_pair(v,f[v]) );
                                                        break;
                                                }
                                        if ( it_PQ == PQ.end() )
                                                PQ.insert ( it_PQ, make_pair(v,f[v]) );
                                        g[v] = 2;
                                }
                                else
                                        for ( it_PQ = PQ.begin(); it_PQ != PQ.end(); ++it_PQ )
                                                if ( v <= (*it_PQ).first )
                                                {
                                                        (*it_PQ).second = f[v];
                                                        break;
                                                }
                        }
                }
        }
        return;
}
void    reroute ( int net_id, routingInst *rst, float factor )
{
        net     *n = rst->nets+net_id;
        int     numPins = n->numPins;
        n->status = 1;

        pin_ordering ( net_id, rst );

        for ( int i = 0; i < numPins-1; i++ )
                A_star_route ( n->r+i, net_id, rst, factor );
        for ( set<int>::iterator it = n->edges.begin(); it!=n->edges.end(); ++it )
        {
                int     id = *it;
                ++ rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight( rst->edgeUtils[id], rst->edgeCaps[id], rst->hist[id] );
        }
}

